import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {

    public static class treeNode {
        treeNode left;
        treeNode right;
        int val;

        public treeNode(int val) {
            this.val = val;
        }
    }

    //根节点
    public static treeNode root;

    public treeNode createBinaryTree() {
        treeNode node1 = new treeNode(1);
        treeNode node2 = new treeNode(2);
        treeNode node3 = new treeNode(3);
        treeNode node4 = new treeNode(4);
        treeNode node5 = new treeNode(5);
        treeNode node6 = new treeNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
        return root;
    }

    //前序遍历
    public void preOrder(treeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
        //前序遍历 先打印根节点 在打印左节点 在打印右节点
        //将大问题拆分成小问题 递归解决
    }

    //中序遍历
    public void inOrder(treeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(treeNode root) {
        if (root == null) return;
        inOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val + " ");
    }

    public int usedSize = 0;

    //获取树中的节点个数
    public int size(treeNode root) {
        if (root == null) {
            return 0;
        }
        usedSize++;
        size(root.left);
        size(root.right);
        return usedSize;
    }

    public int size2(treeNode root) {
        if (root == null) {
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
        //返回值+1是因为要加上根节点
    }

    //获取叶子节点的个数
    public int LeafNodeCount = 0;

    public int getLeafNodeCount(treeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            LeafNodeCount ++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);

        return LeafNodeCount;
    }
    public int getLeafNodeCount2(treeNode root){
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
            //如果是叶子节点 就返回1
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        //返回左树叶子节点的个数和右树叶子节点的个数
    }

    //获取第k层节点的个数
    public int getLevelNodeCount(treeNode root, int k){
        if (root == null){
            return 0;
        }
        if (k == 1){
            return 1;
            //第一层只有一个节点;
        }
        return getLevelNodeCount(root.left, k - 1) + getLevelNodeCount(root.right, k - 1);
    }
    //获取二叉树的高度
    public int getHigh(treeNode root){
        if(root == null){
            return 0;
        }
        int leftHight = getHigh(root.left);
        int rightHight = getHigh(root.right);
        return Math.max(leftHight,rightHight) + 1;
    }

    public int getHigh2(treeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(getHigh2(root.left) , getHigh2(root.right)) + 1;
    }

    public void levelOrder(treeNode root){
        Queue<treeNode> queue = new LinkedList<>();
        if(root != null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            treeNode top = queue.poll();
            System.out.println(top.val);
            if(top.left != null){
                queue.offer(top.left);
            }
            if(top.right != null){
                queue.offer(top.right);
            }
        }
    }

}
